/*
 * Copyright (c) 2018-2022, 四川蜀天梦图数据科技有限公司.
 * All rights reserved.
 */

package dp

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

// 给定n个物品，第i个物品的重量为wgt[i-1],价值为val[i-1]和一个容量为cap的背包。每个物品只能选择一次，问在限定背包容量下能放入物品的最大价值。

// 暴力搜索
func knapsackDFS(wgt, val []int, i, c int) int {
	if i == 0 || c == 0 {
		return 0
	}

	// 表示此次不放入背包中
	if wgt[i-1] > c {
		return knapsackDFS(wgt, val, i-1, c)
	}

	// 不放入背包
	no := knapsackDFS(wgt, val, i-1, c)
	//放入背包
	yes := knapsackDFS(wgt, val, i-1, c-wgt[i-1]) + val[i-1]
	return max(no, yes)
}

func knapsackDFSMem(wgt, val []int, i, c int, mem [][]int) int {
	if i == 0 || c == 0 {
		return 0
	}

	if value := mem[i][c]; value != -1 {
		return value
	}

	// 表示此次不放入背包中
	if wgt[i-1] > c {
		return knapsackDFSMem(wgt, val, i-1, c, mem)
	}

	// 不放入背包
	no := knapsackDFSMem(wgt, val, i-1, c, mem)
	//放入背包
	yes := knapsackDFSMem(wgt, val, i-1, c-wgt[i-1], mem) + val[i-1]
	value := max(no, yes)
	mem[i][c] = value
	return value
}

/* 0-1 背包：动态规划 */
func knapsackDP(wgt, val []int, cap int) int {
	n := len(wgt)
	// 初始化 dp 表
	dp := make([][]int, n+1)
	for i := 0; i <= n; i++ {
		dp[i] = make([]int, cap+1)
	}
	// 状态转移
	for i := 1; i <= n; i++ {
		for c := 1; c <= cap; c++ {
			if wgt[i-1] > c {
				// 若超过背包容量，则不选物品 i
				dp[i][c] = dp[i-1][c]
			} else {
				// 不选和选物品 i 这两种方案的较大值
				dp[i][c] = max(dp[i-1][c], dp[i-1][c-wgt[i-1]]+val[i-1])
			}
		}
	}
	return dp[n][cap]
}

func rob(nums []int) int {
	n := len(nums)

	no, yes, noWith1, yesWith1 := 0, nums[1], nums[0], nums[0]

	//从第二个物品开始
	for i := 3; i <= n; i++ {
		currentNo := max(no, yes)
		currentYes := nums[i-1] + no

		currentNoWith1 := max(noWith1, yesWith1)
		currentYesWith1 := nums[i-1] + noWith1

		no = currentNo
		yes = currentYes

		if i != n {
			noWith1 = currentNoWith1
			yesWith1 = currentYesWith1
		}
	}
	return max(max(no, yes), max(noWith1, yesWith1))
}
